/*************************************************************************
 * File Name:    Linked_List_Cycle.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: Wed 30 Oct 2013 10:39:09 PM CST
 * 
 * Description:  
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <iomanip>

using namespace std;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == NULL) return false;
        
        ListNode *step1, *step2;
        
        step1 = step2 = head;
        while (true) {
            step1 = step1->next;
            
            step2 = step2->next;
            if (step2 == NULL) return false;
            step2 = step2->next;
            if (step2 == NULL) return false;
            
            if (step1 == step2) return true;
        }
    }
};

